package org.xiaojinlong.exam;

/**
 * @author Jin Long
 *         2015/10/17
 */
public class T1510173 {
    private static int counter = 0;
    public static int findMax(int[] a, int lo, int hi) {
        counter++;
        if (lo + 1 == hi)
            return maxOfThree(a[lo], a[hi], a[lo]+a[hi]);
        else {
            int mid = lo + (hi - lo) / 2;
            int leftMax = findMax(a, lo, mid);
            int rightMax = findMax(a, mid+1, hi);
            int midMax = findMaxCrossing(a, lo, mid, hi);
            return maxOfThree(leftMax, rightMax, midMax);
        }
    }

    private static int findMaxCrossing(int[] a, int lo, int mid, int hi) {
        int sum = 0, leftMax = 0;
        for (int i = mid; i >= lo; i--) {
            sum += a[i];
            if (sum > leftMax)
                leftMax = sum;
        }
        sum = 0;
        int rightMax = 0;
        for (int i = mid + 1; i <= hi; i++) {
            sum += a[i];
            if (sum > rightMax)
                rightMax = sum;
        }
        return leftMax + rightMax;
    }

    private static int maxOfThree(int a, int b, int c) {
        if (a > b) {
            if (a > c)
                return a;
            else
                return c;
        } else {
            if (b > c)
                return b;
            else
                return c;
        }
    }

    public static void main(String[] args) {
        int[] a = { 13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7 };
        System.out.println(findMax(a, 0, a.length-1));
        System.out.println(counter);
    }
}
